package day02;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/2 19:42
 */

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 *
 *
 *
 * 输入： heights = [2,4]
 * 输出： 4
 */
public class Solution3 {
    public int largestRectangleArea(int[] heights) {
        LinkedList<Integer> stack = new LinkedList<>();
        int maxS = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty()&&heights[i]<heights[stack.peekLast()]){
                Integer val = stack.pollLast();
                int right = (i - val) * heights[val];
                int left = (stack.isEmpty() ? val : val - stack.peekLast()-1) * heights[val];
                maxS = Math.max(maxS, left + right);
            }
            stack.add(i);
        }
        while (!stack.isEmpty()){
            Integer val = stack.pollLast();
            int right = (heights.length - val) * heights[val];
            int left = (stack.isEmpty() ? val : val - stack.peekLast() -1) * heights[val];
            maxS = Math.max(maxS, left + right);
        }
        return maxS;
    }
}
